double hash Algorithm
sz is the maximum size of the string. first you have to make sure it is right- then you have to call the
calculate_pow() function
- then you can create an object of the
HASH class, and call functions using that object.
- complexity of
create_prefix_hash_table() and hash_total_string() is O(n). And complexity of hash_val() id O(1).
#include <bits/stdc++.h>
using namespace std;
#define FastRead ios_base::sync_with_stdio(false);cin.tie(NULL);
#define sz 20007 // maximum string size
struct hash_pair {
size_t operator()(const pair<int,int>&x)const{
return x.first * 23 + x.second;
}
};
// we are doing double hash, so we are using two base and two mod
#define base1 3207
#define base2 3721
#define mod1 1000003999
#define mod2 1000000861
int pow1[sz+1];
int pow2[sz+1];
void calculate_pow(){
pow1[0] = 1; pow2[0] = 1;
for(int i=1; i<sz; i++){
pow1[i] = (pow1[i-1] *1LL* base1) % mod1;
pow2[i] = (pow2[i-1] *1LL* base2) % mod2;
}
}
class HASH{
int hashV1; int hashV2;
int prefix_hash1[sz+1]; // size = len of string
int prefix_hash2[sz+1];
int calculate_hash(int h, int m, int b, char c){
h = (h*1LL*b) % m;
h = (h*1LL +(c + 1)) % m;// adding 1 so that 0 does not occur
return h;
}
public:
HASH(){
hashV1 = 0; hashV2 = 0;
}
// for a string we are generation two different(double hash) prefix hash array
void create_prefix_hash_table(string s){ // hash table in 0 base index
int ln = s.size();
for(int i=0; i<ln; i++){
hashV1 = calculate_hash(hashV1, mod1, base1, s[i]);
hashV2 = calculate_hash(hashV2, mod2, base2, s[i]);
prefix_hash1[i] = hashV1;
prefix_hash2[i] = hashV2;
}
}
// returning a double hash value for a whole string
pair<int,int> hash_total_string(string s){
hashV1 = 0; hashV2 = 0;
for(int j=0;j<s.size();j++){
hashV1 = calculate_hash(hashV1, mod1, base1, s[j]);
hashV2 = calculate_hash(hashV2, mod2, base2, s[j]);
}
pair<int,int> pr = {hashV1,hashV2};
return pr;
}
// returning double hash value of any substring using previously created prefix_hash_table
pair<int,int> hash_val(int i,int j){// 0 index based query
pair<int,int> pr = {prefix_hash1[j], prefix_hash2[j]};
if(i != 0)
pr = {(mod1*1LL + ((prefix_hash1[j] - prefix_hash1[i-1] *1LL* pow1[j-i+1]) % mod1)) % mod1,
(mod2*1LL + ((prefix_hash2[j] - prefix_hash2[i-1] *1LL* pow2[j-i+1]) % mod2)) % mod2};
return pr;
}
};